package code.c03_stackQueue.sqStack;


/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/10/2 20:18
 * @package code.c03_stackQueue.SqStack
 * @description 设计一个算法，利用顺序栈来检查用户输入的表达式中的括号是否配对（只含有[],(),{}）
 * <p>
 * 思路：遇到左括号立即入栈，遇到右括号弹出栈顶元素，匹配就弹出，不匹配或栈空，说明表达式错误
 */

public class Exam_3_4 {
    public boolean isMatch(String str) {

        int i = 0;
        char e;
        SqStackClass<Character> st = new SqStackClass<>();
        while (i < str.length()) {
            e = str.charAt(i);
            // 所有的左括号进栈
            if (e == '(' || e == '{' || e == '[') {
                st.push(e);
            } else {
                if (e == ')') {
                    if (st.empty()) {
                        return false;
                    }
                    if (st.peek() != '(') {
                        return false;
                    }
                    st.pop();
                }

                if (e == ']') {
                    if (st.empty()) {
                        return false;
                    }
                    if (st.peek() != '[') {
                        return false;
                    }
                    st.pop();
                }

                if (e == '}') {
                    if (st.empty()) {
                        return false;
                    }
                    if (st.peek() != '{') {
                        return false;
                    }
                    st.pop();
                }
            }
            i++;
        }

        // 判断栈是否为空
        return st.empty();
    }

    public static void main(String[] args) {
        Exam_3_4 exam_3_4 = new Exam_3_4();
        System.out.println("()[]{} \t" + exam_3_4.isMatch("()[]{}"));
        System.out.println("()[){} \t" + exam_3_4.isMatch("()[){}"));
    }
}
